
#include <stdio.h>
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {

        }
};


struct ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2 )
{
    if(pHead1==NULL||pHead2==NULL)
    {
        return NULL;
    }
    //判断有没有环
    ListNode * fast1=pHead1;
    ListNode * slow1=pHead1;
    ListNode * fast2=pHead2;
    ListNode * slow2=pHead2;

    ListNode * pos_1=NULL;
    ListNode * pos_2=NULL;

    int len_1=0;
    int len_2=0;

    while(fast1!=NULL)
    {
        slow1=slow1->next;
        if(fast1->next==NULL)
        {
            len_1+=1;
            break;
        }
        fast1=fast1->next->next;
        if(fast1==slow1)
        {//有环
            pos_1=fast1;
        }
        len_1=len_1+2;
    }

    while(fast2!=NULL)
    {
        slow2=slow2->next;
        if(fast2->next==NULL)
        {
            len_2+=1;
            break;
        }
        fast2=fast2->next->next;
        if(fast2==slow2)
        {
            pos_2=fast2;
            break;
        }
        len_2+=2;
    }
    
    if(pos_1==NULL&&pos_2==NULL)
    {//说明两个都没有环
        fast1=pHead1;
        fast2=pHead2;
        if(len_1>len_2)
        {
            int i=0;
            while(i<len_1-len_2)
            {
                fast1=fast1->next;
                i++;
            }
            while(fast1!=NULL&&fast2!=NULL)
            {
                if(fast1==fast2)
                {
                    return fast1;
                }
                fast1=fast1->next;
                fast2=fast2->next;
            }
        }
        else
        {
            int i=0;
            while(i<len_2-len_1)
            {
                fast2=fast2->next;
                i++;
            }
            while(fast1!=NULL&&fast2!=NULL)
            {
                if(fast1==fast2)
                {
                    return fast2;
                }
                fast1=fast1->next;
                fast2=fast2->next;
            }

        }
    }
    else
    {
        if(pos_1&&pos_2)//说明两个都有环
        {

        }
        else
        {//一个有环，一个没有环，是不可能有交点的

        }
    }
    return NULL;

}
void test()
{
    ListNode * pos_1=new ListNode(1);
    ListNode * pos_2=new ListNode(2);
    ListNode * pos_3=new ListNode(3);
    ListNode * pos_4=new ListNode(4);
    ListNode * pos_5=new ListNode(5);

    pos_1->next=pos_2;
    pos_2->next=pos_3;
    pos_3->next=pos_4;
    pos_4->next=pos_5;

    ListNode * pos_11=new ListNode(11);
    ListNode * pos_22=new ListNode(22);
    ListNode * pos_33=new ListNode(33);
    ListNode * pos_44=new ListNode(44);
    ListNode * pos_55=new ListNode(55);

    pos_11->next=pos_22;
    pos_22->next=pos_33;
    pos_33->next=pos_44;
    pos_44->next=pos_55;
        

    pos_5->next=pos_55;

    ListNode * ret=FindFirstCommonNode(pos_1,pos_11);
    if(ret)
    {
        cout<<ret->val<<endl;
    }

}
int main()
{
    test();
    return 0;
}
